#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STR_LEN 1000010  
#define MAX_OP_COUNT 1000010 

typedef struct 
{
    char** strings;  
    int capacity;     
    int size;          
} MinHeap;

MinHeap* createMinHeap(int capacity)
{
    MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
    heap->capacity = capacity;
    heap->size = 0;
    heap->strings = (char**)malloc(capacity * sizeof(char*));
    return heap;
}

void swap(char** a, char** b)
{
    char* temp = *a;
    *a = *b;
    *b = temp;
}

void swim(MinHeap* heap, int index) 
{
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (strcmp(heap->strings[index], heap->strings[parent]) < 0)
        {
            swap(&heap->strings[index], &heap->strings[parent]);
            index = parent;
        }
        else 
        {
            break;
        }
    }
}

void sink(MinHeap* heap, int index) 
{
    while (2 * index + 1 < heap->size) 
    {
        int left = 2 * index + 1;
        int right = left + 1;
        int min_child = left;

        if (right < heap->size &&
            strcmp(heap->strings[right], heap->strings[left]) < 0) 
        {
            min_child = right;
        }

        if (strcmp(heap->strings[min_child], heap->strings[index]) < 0) 
        {
            swap(&heap->strings[index], &heap->strings[min_child]);
            index = min_child;
        }
        else 
        {
            break;
        }
    }
}

void insert(MinHeap* heap, char* s) 
{
    char* new_str = (char*)malloc((strlen(s) + 1) * sizeof(char));
    strcpy_s(new_str, s,5555);

    heap->strings[heap->size] = new_str;
    swim(heap, heap->size);
    heap->size++;
}

char* getMin(MinHeap* heap) 
{
    if (heap->size == 0) return NULL;
    return heap->strings[0];
}

void deleteMin(MinHeap* heap)
{
    if (heap->size == 0) return;

    free(heap->strings[0]);

    heap->strings[0] = heap->strings[heap->size - 1];
    heap->size--;

    if (heap->size > 0) 
    {
        sink(heap, 0);
    }
}

void freeHeap(MinHeap* heap)
{
    for (int i = 0; i < heap->size; i++) 
    {
        free(heap->strings[i]);
    }
    free(heap->strings);
    free(heap);
}

int main()
{
    int n;
    scanf_s("%d", &n);  

    MinHeap* heap = createMinHeap(MAX_OP_COUNT);

    char buffer[MAX_STR_LEN];

    for (int i = 0; i < n; i++) 
    {
        int op;
        scanf_s("%d", &op); 

        if (op == 1) 
        {
            scanf_s("%s", buffer);
            insert(heap, buffer);
        }
        else if (op == 2) 
        {
            char* min_str = getMin(heap);
            printf("%s\n", min_str);
        }
        else if (op == 3)
        {
            deleteMin(heap);
        }
    }

    freeHeap(heap);

    return 0;
}